package com.itheima.search;

public class A03_BlockSearchDemo2 {
    public static void main(String[] args) {
        int[] arr = {27, 22, 30, 40, 36,
                13, 19, 16, 20,
                7, 10,
                43, 50, 48};

        //创建三个Block对象
        Block2 b1 = new Block2(22, 40, 0, 4);
        Block2 b2 = new Block2(13, 20, 5, 8);
        Block2 b3 = new Block2(7, 10, 9, 10);
        Block2 b4 = new Block2(43, 50, 11, 13);

        //定义一个变量用来记录要查找的元素
        int number = 48;

        //创建一个Block对象的数组用来管理三个块的对象（索引表）
        Block2[] blockArr = {b1, b2, b3, b4};


        //调用方法，传递索引表，数组，要查找的元素
        int index = getIndex(blockArr, arr, number);

        //打印一下
        System.out.println(index);
    }

    //利用分块查找的原理，查询number的索引

    public static int getIndex(Block2[] blockArr, int[] arr, int number) {
        //1.确定number是在哪一块当中
        int index = findIndexBlock(blockArr, number);

        if (index < 0) {
            //表示number不在数组当中
            return -1;
        }

        //2.获取这一块的起始索引和结束索引
        int startIndex = blockArr[index].getStartindex();
        int endIndex = blockArr[index].getEndindex();

        //3.遍历
        for (int i = startIndex; i <= endIndex; i++) {
            if (arr[i] == number) {
                return i;
            }
        }
        return -1;
    }

    //定义一个方法，用来确定number在哪一块当中
    public static int findIndexBlock(Block2[] blockArr, int number) {
        //Block2 b1 = new Block2(22,40,0,4);   ----0
        //Block2 b2 = new Block2(13,20,5,8);   ----1
        //Block2 b3 = new Block2(7,10,9,10);   ----2
        //Block2 b4 = new Block2(43,50,11,13); ----3

        //从0索引开始遍历blockArr，如果number是在max和min之间，那么就表示number是在这一块当中的
        for (int i = 0; i < blockArr.length; i++) {
            if (blockArr[i].getMax() > number && blockArr[i].getMin() < number) {
                return i;
            }
        }
        return -1;
    }
}

class Block2 {
    private int min;
    private int max;
    private int startindex;
    private int endindex;

    public Block2() {
    }

    public Block2(int min, int max, int startindex, int endindex) {
        this.min = min;
        this.max = max;
        this.startindex = startindex;
        this.endindex = endindex;
    }

    public int getMin() {
        return min;
    }

    public void setMin(int min) {
        this.min = min;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStartindex() {
        return startindex;
    }

    public void setStartindex(int startindex) {
        this.startindex = startindex;
    }

    public int getEndindex() {
        return endindex;
    }

    public void setEndindex(int endindex) {
        this.endindex = endindex;
    }
}

